package com.huangkailong.leetcode;

/**
 * 给定两个大小分别为 m 和 n 的正序（从小到大）数组nums1 和nums2。请你找出并返回这两个正序数组的 中位数 。<br/>
 * <br/>
 * 示例 1：<br/>
 * 输入：nums1 = [1,3], nums2 = [2]<br/>
 * 输出：2.00000<br/>
 * 解释：合并数组 = [1,2,3] ，中位数 2<br/>
 * <br/>
 * 示例 2：<br/>
 * 输入：nums1 = [1,2], nums2 = [3,4]<br/>
 * 输出：2.50000<br/>
 * 解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5<br/>
 * <br/>
 * 示例 3：<br/>
 * 输入：nums1 = [0,0], nums2 = [0,0]<br/>
 * 输出：0.00000<br/>
 * <br/>
 * 示例 4：<br/>
 * 输入：nums1 = [], nums2 = [1]<br/>
 * 输出：1.00000<br/>
 * <br/>
 * 示例 5：<br/>
 * 输入：nums1 = [2], nums2 = []<br/>
 * 输出：2.00000<br/>
 * <br/>
 * 提示：<br/>
 * nums1.length == m<br/>
 * nums2.length == n<br/>
 * 0 <= m <= 1000<br/>
 * 0 <= n <= 1000<br/>
 * 1 <= m + n <= 2000<br/>
 * -106 <= nums1[i], nums2[i] <= 106<br/>
 *<br/>
 * 进阶：你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗？<br/>
 * 
 * @author huangkl
 * @date 2021-04-27 9:51
 */
public class MedianSortedArraysFind {

    /**
     * 通过把两个有序数组合并成一个有序数组，然后从合并后的有序数组中找到中位数
     * 时间复杂度：O(m+n), m 为 nums1 长度, n 为 nums2 长度
     * 空间复杂度：O(m+n), m 为 nums1 长度, n 为 nums2 长度
     */
    public static double solution1(int[] nums1, int[] nums2) {
        int totalLen = nums1.length + nums2.length;
        int position = totalLen/2;
        boolean isEvenNumber = false;
        if(totalLen % 2 == 0){
            isEvenNumber = true;
        }

        int count = 0;
        int i = 0;
        int j = 0;
        int[] result = new int[position+1];
        int resultLen = result.length;
        while (count < resultLen){
            if(i < nums1.length && j < nums2.length){
                if(nums1[i] < nums2[j]){
                    result[count] = nums1[i];
                    i++;
                }else if(nums1[i] == nums2[j]){
                    result[count] = nums1[i];
                    i++;
                }else {
                    result[count] = nums2[j];
                    j++;
                }
            }else if(i < nums1.length){
                result[count] = nums1[i];
                i++;
            }else {
                result[count] = nums2[j];
                j++;
            }
            count++;
        }

        return isEvenNumber ? (result[resultLen-1]+result[resultLen-2])*1.0/2 : result[resultLen-1];
    }

    /**
     * 二分查找
     *
     */
    public static double solution2(int[] nums1, int[] nums2) {
        int totalLength = nums1.length + nums2.length;

        // 1 2 3 4 5 6 7 8 -> mid = 4，中位数为第 4 个数和 第 5 个数之和的平均值
        // 1 2 3 4 5 6 7 -> mid = 3，中位数为第 4 个数
        int mid = totalLength/2;
        if(totalLength % 2 == 0){
            // 总数为偶数
            return (getKthNum(nums1, nums2, mid)+getKthNum(nums1, nums2, mid+1))/2.0;
        }else {
            // 总数为奇数
            return getKthNum(nums1, nums2, mid+1);
        }
    }


    /**
     * 主要思路：要找到第 k (k>1) 小的元素，那么就取 pivot1 = nums1[k/2-1] 和 pivot2 = nums2[k/2-1] 进行比较<br/>
     * 这里的 "/" 表示整除<br/>
     * nums1 中小于等于 pivot1 的元素有 nums1[0 .. k/2-2] 共计 k/2-1 个<br/>
     * nums2 中小于等于 pivot2 的元素有 nums2[0 .. k/2-2] 共计 k/2-1 个<br/>
     * 取 pivot = min(pivot1, pivot2)，两个数组中小于等于 pivot 的元素共计不会超过 (k/2-1) + (k/2-1) <= k-2 个<br/>
     * 这样 pivot 本身最大也只能是第 k-1 小的元素<br/>
     * 如果 pivot = pivot1，那么 nums1[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 "删除"，剩下的作为新的 nums1 数组<br/>
     * 如果 pivot = pivot2，那么 nums2[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 "删除"，剩下的作为新的 nums2 数组<br/>
     * 由于我们 "删除" 了一些元素（这些元素都比第 k 小的元素要小），因此需要修改 k 的值，减去删除的数的个数<br/>
     * <br/>
     * 获取有序数组 nums1 和有序数组 nums2 合并后第 k 小的数
     * @param nums1 有序数组 1
     * @param nums2 有序数组 2
     * @param kth 数位置
     * @return 有序数组 nums1 和有序数组 nums2 合并后第 k 小的数
     */
    public static int getKthNum(int[] nums1, int[] nums2, int kth){
        int index1 = 0;
        int index2 = 0;
        int k = kth;
        while (true){
            if(index1 == nums1.length){
                // 返回 nums2 第 index2+k 小的数，-1 是因为数组从 0 开始，所以 index2+k 小的数数组下标为 index2+k-1
                return nums2[index2+k-1];
            }
            if(index2 == nums2.length){
                // 返回 nums1 第 index1+k 小的数，-1 是因为数组从 0 开始，所以 index1+k 小的数数组下标为 index1+k-1
                return nums1[index1+k-1];
            }
            if(k == 1){
                // 返回两个有序数组第 1 小的数
                // 等价于 Math.min(nums1[index1+1-1], nums2[index2+1-1])
                return Math.min(nums1[index1], nums2[index2]);
            }


            int half = k/2;
            // -1 是因为第 half 小的数，数组下标为 half-1
            int newIndex1 = Math.min(half+index1, nums1.length)-1;
            int newIndex2 = Math.min(half+index2, nums2.length)-1;
            int pivot1 = nums1[newIndex1], pivot2 = nums2[newIndex2];
            if(pivot1 <= pivot2){
                // k 减去被排除的数，newIndex1-index1 不包括 index1 ，所以要 +1
                k -= (newIndex1-index1)+1;
                index1 = newIndex1+1;
            }else {
                k -= (newIndex2-index2)+1;
                index2 = newIndex2+1;
            }
        }
    }
}
